package funmath;

/**
 * 约瑟夫环问题:
 * 罗马人攻占了乔塔帕特，41个人藏在一个山洞中躲过了这场浩劫。这41个人中，包括历史学家Josephus(约瑟夫)和他的一个朋友
 * ，剩余的39个人为了表示不想罗马人屈服，决定集体自杀。大家决定了一个自杀方案，所有者41个人围城圆圈，由第1个热年开始顺时针报数，每报数为3的人就立刻自杀，然后再由下一个人重新开始报数，仍然是每报数为3的人就立刻自杀，......,知道所有
 * 的人都自杀身亡为止。
 * 约瑟夫和他的朋友并不像自杀，于是约瑟夫想到了一个计策，他们两个同样参与到自杀方案中，但是最后却躲过了自杀，请问，
 *   他们是怎么做到的？
 */
public class Josephus {
    static final int NUM = 41;//总人数
    static final int KILL_MAN = 3;//自杀者报数
   public static void main(String[] args){
       josephus(2);
   }
    /**
     *
     * @param alive
     */
    public static void josephus(int alive){
        int[] man = new int[NUM];
        int count = 1;//被干掉的人数
        int i=0;//记录第几个人如果是第三个人就设置为0，每三个人一轮
        int pos = -1;
        while(count<=NUM){
            //内层循环寻找应该被干掉的第三个人
            do{
                pos=(pos+1)%NUM;    //环处理---这个公式是如果超过总数了就会跑到开头不会出现大于总数的数字
                if(man[pos]==0){  //只计算没被干掉的i数字才能递增
                    i++;
                }
                if(i==KILL_MAN){ //如果是第三个人就将i设置为0 跳出循环
                    i = 0;
                    break;
                }
            }while(true);

            man[pos] = count;//被干掉的人数组数据为1
            System.out.printf("第%2d个人自杀！约瑟夫环编号为%2d",pos+1,man[pos]);
            if(count%2 == 1){
                System.out.printf("->");
            }else{
                System.out.printf("->\n");//输出换行
            }
            count++;//干掉一个人计数器加1
        }
        System.out.printf("\n");
        System.out.printf("这%d需要存活的人初始位置应该排在以下序号:\n",alive);
        alive = NUM-alive;
        for(int j=0;j<NUM;j++){
            if(man[j]>alive){
                System.out.printf("初始编号:%d,约瑟夫环编号:%d\n",i+1,man[i]);
            }
        }
        System.out.printf("\n");
    }

}
